#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_DICT_SIZE 4096
#define ASCII_SIZE 256
#define MAX_CODE_SIZE 12 // 假设最大码字长度为12位

typedef struct
{
    unsigned int code;
    char str[256];
} DictEntry;

DictEntry dict[MAX_DICT_SIZE];
unsigned int dictSize = ASCII_SIZE; // 初始字典大小为ASCII字符数

// 初始化字典，只包含单个字符的条目
void initDictionary()
{
    for (int i = 0; i < ASCII_SIZE; ++i)
    {
        dict[i].code = i;
        dict[i].str[0] = (char)i;
        dict[i].str[1] = '\0';
    }
}

// 查找字符串在字典中的代码
unsigned int findEntry(const char *str)
{
    for (unsigned int i = 0; i < dictSize; ++i)
    {
        if (strcmp(dict[i].str, str) == 0)
        {
            return i;
        }
    }
    return MAX_DICT_SIZE; // 未找到
}

// 将新字符串添加到字典
void addEntry(const char *str)
{
    if (dictSize < MAX_DICT_SIZE)
    {
        strcpy(dict[dictSize].str, str);
        dict[dictSize].code = dictSize;
        dictSize++;
    }
}

// 将码字写入文件，按位操作
void writeCode(unsigned int code, FILE *outputFile)
{
    for (int i = MAX_CODE_SIZE - 1; i >= 0; --i)
    {
        // 写入当前位
        fputc((code >> i) & 1, outputFile);
    }
}

// LZW压缩函数
void lzwCompress(const char *inputString, FILE *outputFile)
{
    char currentString[256] = {0};
    char nextChar;
    unsigned int currentCode, nextCode;

    currentString[0] = inputString[0];
    currentCode = (unsigned int)(unsigned char)inputString[0];

    for (int i = 1; inputString[i] != '\0'; ++i)
    {
        nextChar = inputString[i];
        currentString[1] = nextChar;
        nextCode = findEntry(currentString);

        if (nextCode != MAX_DICT_SIZE)
        {
            currentCode = nextCode;
        }
        else
        {
            writeCode(currentCode, outputFile);
            addEntry(currentString);
            currentCode = (unsigned int)(unsigned char)nextChar;
        }

        currentString[0] = nextChar;
    }

    writeCode(currentCode, outputFile); // 输出最后一个代码
}

int main()
{
    FILE *inputFile = fopen("input.txt", "r");
    FILE *outputFile = fopen("compressed.lzw", "wb"); // 以二进制模式打开

    if (inputFile == NULL)
    {
        perror("Error opening input file");
        return 1;
    }

    if (outputFile == NULL)
    {
        perror("Error opening output file");
        fclose(inputFile); // 关闭已经打开的输入文件
        return 1;
    }

    // 读取输入文件内容
    fseek(inputFile, 0, SEEK_END);
    long length = ftell(inputFile);
    fseek(inputFile, 0, SEEK_SET);
    char *inputString = malloc(length + 1);
    if (inputString)
    {
        fread(inputString, 1, length, inputFile);
        inputString[length] = '\0'; // 确保字符串以空字符结尾
    }
    else
    {
        perror("Memory allocation failed");
        fclose(inputFile);
        fclose(outputFile);
        return 1;
    }

    initDictionary();
    lzwCompress(inputString, outputFile);

    free(inputString); // 释放分配的内存
    fclose(inputFile);
    fclose(outputFile);
    return 0;
}